 /*******************************************************************************
  * Copyright (c) 2000, 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.events;

 import org.eclipse.core.runtime.IPath;

 /**
  * A specialized map that maps Node IDs to their old and new paths.
  * Used for calculating moves during resource change notification.
  */
 public class NodeIDMap {
     //using prime table sizes improves our hash function
 private static final int[] SIZES = new int[] {13, 29, 71, 173, 349, 733, 1511, 3079, 6133, 16381, 32653, 65543, 131111, 262139, 524287, 1051601};
     private static final double LOAD_FACTOR = 0.75;
     //2^32 * golden ratio
 private static final long LARGE_NUMBER = 2654435761L;

     int sizeOffset = 0;
     protected int elementCount = 0;
     protected long[] ids;
     protected IPath[] oldPaths;
     protected IPath[] newPaths;

     /**
      * Creates a new node ID map of default capacity.
      */
     public NodeIDMap() {
         this.sizeOffset = 0;
         this.ids = new long[SIZES[sizeOffset]];
         this.oldPaths = new IPath[SIZES[sizeOffset]];
         this.newPaths = new IPath[SIZES[sizeOffset]];
     }

     /**
      * The array isn't large enough so double its size and rehash
      * all its current values.
      */
     protected void expand() {
         int newLength;
         try {
             newLength = SIZES[++sizeOffset];
         } catch (ArrayIndexOutOfBoundsException e) {
             //will only occur if there are > 1 million elements in delta
 newLength = ids.length * 2;
         }
         long[] grownIds = new long[newLength];
         IPath[] grownOldPaths = new IPath[newLength];
         IPath[] grownNewPaths = new IPath[newLength];
         int maxArrayIndex = newLength - 1;
         for (int i = 0; i < ids.length; i++) {
             long id = ids[i];
             if (id != 0) {
                 int hash = hashFor(id, newLength);
                 while (grownIds[hash] != 0) {
                     hash++;
                     if (hash > maxArrayIndex)
                         hash = 0;
                 }
                 grownIds[hash] = id;
                 grownOldPaths[hash] = oldPaths[i];
                 grownNewPaths[hash] = newPaths[i];
             }
         }
         ids = grownIds;
         oldPaths = grownOldPaths;
         newPaths = grownNewPaths;
     }

     /**
      * Returns the index of the given element in the map. If not
      * found, returns -1.
      */
     private int getIndex(long searchID) {
         final int len = ids.length;
         int hash = hashFor(searchID, len);

         // search the last half of the array
 for (int i = hash; i < len; i++) {
             if (ids[i] == searchID)
                 return i;
             // marker info not found so return -1
 if (ids[i] == 0)
                 return -1;
         }

         // search the beginning of the array
 for (int i = 0; i < hash - 1; i++) {
             if (ids[i] == searchID)
                 return i;
             // marker info not found so return -1
 if (ids[i] == 0)
                 return -1;
         }
         // marker info not found so return -1
 return -1;
     }

     /**
      * Returns the new path location for the given ID, or null
      * if no new path is available.
      */
     public IPath getNewPath(long nodeID) {
         int index = getIndex(nodeID);
         if (index == -1)
             return null;
         return newPaths[index];
     }

     /**
      * Returns the old path location for the given ID, or null
      * if no old path is available.
      */
     public IPath getOldPath(long nodeID) {
         int index = getIndex(nodeID);
         if (index == -1)
             return null;
         return oldPaths[index];
     }

     private int hashFor(long id, int size) {
         //Knuth's hash function from Art of Computer Programming section 6.4
 return (int) Math.abs((id * LARGE_NUMBER) % size);
     }

     /**
      * Returns true if there are no elements in the map, and
      * false otherwise.
      */
     public boolean isEmpty() {
         return elementCount == 0;
     }

     /**
      * Adds the given path mappings to the map. If either oldPath
      * or newPath is null, they are ignored (old map values are not overwritten).
      */
     private void put(long id, IPath oldPath, IPath newPath) {
         if (oldPath == null && newPath == null)
             return;
         int hash = hashFor(id, ids.length);

         // search for an empty slot at the end of the array
 for (int i = hash; i < ids.length; i++) {
             if (ids[i] == id) {
                 //replace value for existing entry
 if (oldPath != null)
                     oldPaths[i] = oldPath;
                 if (newPath != null)
                     newPaths[i] = newPath;
                 return;
             }
             if (ids[i] == 0) {
                 //add a new entry to the map
 ids[i] = id;
                 if (oldPath != null)
                     oldPaths[i] = oldPath;
                 if (newPath != null)
                     newPaths[i] = newPath;
                 elementCount++;
                 // grow if necessary
 if (shouldGrow())
                     expand();
                 return;
             }
         }

         // search for an empty slot at the beginning of the array
 for (int i = 0; i < hash - 1; i++) {
             if (ids[i] == id) {
                 //replace value for existing entry
 if (oldPath != null)
                     oldPaths[i] = oldPath;
                 if (newPath != null)
                     newPaths[i] = newPath;
                 return;
             }
             if (ids[i] == 0) {
                 //add a new entry to the map
 ids[i] = id;
                 if (oldPath != null)
                     oldPaths[i] = oldPath;
                 if (newPath != null)
                     newPaths[i] = newPath;
                 elementCount++;
                 // grow if necessary
 if (shouldGrow())
                     expand();
                 return;
             }
         }
         // if we didn't find a free slot, then try again with the expanded set
 expand();
         put(id, oldPath, newPath);
     }

     /**
      * Adds an entry for a node's old path
      */
     public void putOldPath(long id, IPath path) {
         put(id, path, null);
     }

     /**
      * Adds an entry for a node's old path
      */
     public void putNewPath(long id, IPath path) {
         put(id, null, path);
     }

     private boolean shouldGrow() {
         return elementCount > ids.length * LOAD_FACTOR;
     }
 }

